n=100;
m=100;
p=[55582,23430,68987,9235,96673,5900,46531,2404,88147,18008,32901,37446,16779,79193,29913,27560,67547,18055,24431,95805,18886,2392,90346,71413,90672,51607,17450,70405,38397,4364,33974,70213,7975,22239,50020,37243,17017,87638,62482,89960,85321,19744,23124,16864,14995,97377,39836,82395,56960,85568,74074,6908,86910,25362,27092,15864,10397,23503,97625,5674,58266,22431,70278,4396,71903,17542,1904,84164,80720,93312,20510,92563,38555,56367,18560,9420,14968,51367,77520,21852,49107,99519,49859,33024,12308,49716,41808,37823,62129,53457,5644,39364,56618,28446,66812,51634,73156,68580,67251,42137];
road=[|2,1|
3,1|
4,1|
5,1|
6,1|
7,1|
8,1|
9,1|
10,1|
11,9|
12,9|
13,11|
14,11|
15,14|
16,13|
17,15|
18,16|
19,17|
20,17|
21,20|
22,20|
23,22|
24,22|
25,22|
26,25|
27,24|
28,25|
29,27|
30,28|
31,30|
32,31|
33,32|
34,31|
35,33|
36,34|
37,36|
38,35|
39,37|
40,37|
41,38|
42,41|
43,41|
44,41|
45,42|
46,44|
47,45|
48,46|
49,47|
50,48|
51,48|
52,50|
53,52|
54,52|
55,54|
56,54|
57,56|
58,56|
59,58|
60,57|
61,58|
62,60|
63,60|
64,61|
65,62|
66,63|
67,64|
68,67|
69,68|
70,68|
71,68|
72,69|
73,71|
74,73|
75,73|
76,73|
77,75|
78,76|
79,78|
80,77|
81,79|
82,79|
83,80|
84,81|
85,83|
86,83|
87,84|
88,86|
89,88|
90,87|
91,89|
92,90|
93,90|
94,91|
95,93|
96,93|
97,96|
98,95|
99,98|
100,97|];
request=[|53,0,7,0|
81,1,62,1|
96,0,2,0|
7,0,49,0|
71,0,58,1|
1,1,42,0|
58,0,82,1|
43,0,30,0|
63,1,53,1|
88,1,31,1|
68,1,42,1|
63,0,68,0|
61,1,16,1|
20,0,60,1|
17,0,1,0|
39,1,22,0|
57,1,6,0|
20,0,91,1|
19,0,10,0|
1,0,90,1|
91,1,83,1|
48,1,85,0|
16,1,30,1|
88,1,40,1|
17,1,27,1|
66,0,21,1|
83,1,57,1|
39,0,50,1|
44,0,77,0|
53,0,13,0|
25,0,15,0|
26,0,71,0|
33,0,36,0|
70,0,18,0|
90,1,50,1|
41,0,37,0|
31,0,80,1|
98,1,81,1|
42,1,30,0|
23,1,34,1|
72,0,84,1|
98,1,19,0|
47,1,11,0|
68,1,33,0|
63,0,25,1|
97,1,29,0|
79,0,15,1|
82,0,99,1|
90,0,89,1|
38,0,75,0|
57,0,62,0|
13,0,28,1|
68,0,26,0|
23,0,34,1|
61,0,67,0|
96,1,75,1|
93,1,21,0|
77,1,30,1|
35,0,27,1|
52,0,14,0|
36,1,25,0|
10,1,61,1|
44,0,89,0|
93,0,71,0|
66,1,32,1|
84,1,96,0|
55,0,42,0|
97,0,86,0|
41,0,78,0|
33,1,78,1|
48,0,61,0|
29,0,81,1|
18,1,56,0|
32,0,5,1|
66,1,22,0|
75,0,54,1|
74,1,43,0|
81,1,75,1|
54,1,46,1|
64,1,86,0|
65,1,37,1|
10,1,18,1|
49,0,53,1|
32,0,36,1|
28,0,90,0|
29,0,80,1|
43,0,48,0|
81,0,78,1|
21,0,97,0|
62,1,67,0|
3,0,79,1|
77,0,2,0|
74,1,27,1|
5,1,36,1|
67,0,80,0|
67,0,70,0|
68,1,64,0|
74,0,7,1|
47,1,55,0|
4,0,74,1|];